package com.practice.string;

public class FirstPalindrome {
	private final static int MOD = 1000000007;
	
	public int first(int[] a) {
		int pow3 = 1;
		int hash = a[0];
		int reverse = a[0];
		
		for (int i=1; i<a.length; i++) {
			pow3 = (pow3 * 3) % MOD;
			hash = (hash + a[i] * pow3) % MOD;
			reverse = (3*reverse + a[i]) % MOD;
			
			if (hash == reverse && test(a, i)) return i;
		}
		
		return -1;
	}
	
	private boolean test(int[] a, int i) {
		for (int j=0; j<i/2; j++) {
			if (a[j] != a[i-j]) return false;
		}
		return true;
	}
}
